We study the problem of inverting a deep generative model with ReLU activations. Inversion corresponds to finding a latent code vector that explains observed measurements as much as possible. In most prior works this is performed by attempting to solve a non-convex optimization problem involving the generator. In this paper we obtain several novel theoretical results for the inversion problem. We show that for the realizable case, single layer inversion can be performed exactly in polynomial time, by solving a linear program.

We study the problem of inverting a deep generative model with ReLU activations. Inversion corresponds to finding a latent code vector that explains observed measurements as much as possible. In most prior works this is performed by attempting to solve a non-convex optimization problem involving the generator. In this paper we obtain several novel theoretical results for the inversion problem. We show that for the realizable case, single layer inversion can be performed exactly in polynomial time, by solving a linear program.

Theorem 1 states "The [Recovery of a binary latent code from a two-layer ReLU] is NP-hard since it could be reduced to MAX-3SAT problem." For an NP-hardness proof, what one wishes to show is a reduction _from_ the known NP-hard problem _to_ the problem being studied. The proof in the appendix appears to correctly use the proposed recovery algorithm as a gadget in solving MAX3SAT, which would be sufficient for an NP-hardness proof, but the text is inconsistent with the theoretical results given. Additionally, while the binary reconstruction problem is interesting for the purpose of the complexity proof, it would be helpful to the reviewers if the rationale for this choice was made clearer outside of the context of the proof and while it is not strictly necessary for the theoretical results it would be useful if it could be shown that the binary latent variable case was representative of the complexity of the problem in general. It is unclear where the expansiveness requirement for the generator model fits into the proof of Theorem 2 The only competing method examined is a strawman version of gradient descent, it would be interesting to see how this method compares to other approaches. Should the inequality in equation 4 be wTz b 0? I'm confused about the dimensions of W and how it relates to both x and z.

This theoretical paper studied the invertibility of ReLU networks, as generative priors for denoising or compressive sensing. The invertibility of networks with random weights one layer at a time is also investigated and interesting stability bounds are also provided. Note: comments made by Reviewer #2 should be incorporated for the camera ready version.

We study the problem of inverting a deep generative model with ReLU activations. Inversion corresponds to finding a latent code vector that explains observed measurements as much as possible. In most prior works this is performed by attempting to solve a non-convex optimization problem involving the generator. In this paper we obtain several novel theoretical results for the inversion problem. We show that for the realizable case, single layer inversion can be performed exactly in polynomial time, by solving a linear program.

We study the problem of inverting a deep generative model with ReLU activations. Inversion corresponds to finding a latent code vector that explains observed measurements as much as possible. In most prior works this is performed by attempting to solve a non-convex optimization problem involving the generator. In this paper we obtain several novel theoretical results for the inversion problem. We show that for the realizable case, single layer inversion can be performed exactly in polynomial time, by solving a linear program.